package sword.offer;

import sword.offer.common.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，
 * 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 * 链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class SixtyEight {
    /**
     * 我能想到的最直接的方式 就是拿到这两个结点的路径
     * 然后比较路径中相同的元素，排在后面的深度越大。
     * */
    class Solution {
       
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            List<TreeNode> pathA = new ArrayList<>(), pathB = new ArrayList<>();
            TreeNode val = null;
            getPath(root, pathA, p);
            getPath(root, pathB, q);
            for (int i = 0; i < Math.min(pathA.size(), pathB.size()); i++) {
                if(pathA.get(i).val != pathB.get(i).val){
                    return val;
                }
                val = pathA.get(i);
            }
            return val;
        }
        
        private void getPath(TreeNode curNode, List<TreeNode> path, TreeNode node){
            if(curNode.val == node.val){
                path.add(curNode);
                return ;
            }
            path.add(curNode);
            if(curNode.val > node.val){
                getPath(curNode.left, path, node);
            }else{
                getPath(curNode.right, path, node);
            }
        }
    }

    /**
     * 一次遍历
     * 其实判断p和q的最近的公共祖先结点，只要知道他们从哪里开始 '分家' 就行了
     *
     * */
    class Solution1 {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if(root == null){
                return null;
            }
            if(p.val > root.val && q.val > root.val){
                return lowestCommonAncestor(root.right, p, q);
            }

            if(p.val < root.val && q.val < root.val){
                return lowestCommonAncestor(root.left, p, q);
            }
            return root;
        }
    }
}
